package code1_100.code60_70;

/**
 * 70 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 *
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 *
 */
public class _70ClimbFloor {

    /**
     * 输入台阶数N，初始想法是考虑排列组合。
     * 先想到上N层台阶所有的步数可能性，left = n/2(每次走两层)，right = n(每次走一层)
     * 然后对每种可能性，取C(n.k)组合，算出可能性
     *
     * 总结：此方法算法上可行，但时间O(n!)和空间复杂度太难，代码难以编写，故卡住了！
     * @param n
     * @return
     */
    /*public static int climbStairs(int n) {
        int left = n%2==0?n/2:(n/2)+1;
        int right = n;
        int result = 0;
        for (int i = 1; i <= right - left; i++) {
            // 组合 ： C(n, k) = n! / (k! * (n-k)!)
            result += (right-left);
        }
        return result;
    }*/

    /**
     * 观看题解，是一道经典的动态规划问题。动态规划描述：最优解可以分解为若干个子问题的最优解。
     * 对于此题，爬楼梯是一层一层爬的，故可分为子问题。同时得到F(n) = F(n-1) + F(n-2)
     * 这就转换为了斐波那契数列问题，有多种解决方案
     *
     * 下述方法直接注册大量数组空间进行求解，时间复杂度为O(1),空间复杂度为O(n)，适合小批量作业。如果需要空间复杂度降低，需使用滚动数组。
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：35.3 MB, 在所有 Java 提交中击败了25.46% 的用户
     * 通过测试用例：45 / 45
     * @param n
     * @return
     */
    /*public static int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n-1];
    }*/

    /**
     * 滚动数组测试
     *
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：35.1 MB, 在所有 Java 提交中击败了69.53% 的用户
     * 通过测试用例：45 / 45
     *
     * 测试结果显示，有较好的性能提升
     *
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int first = 1;
        int second = 2;
        int third = 0;
        for (int i = 2; i < n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }




    public static void main(String[] args) {
        System.out.println(climbStairs(10));
    }
}
